package everydayGrade.t3;

/**
 * @Author: Siantar
 * @Date: 2023-10-02-14:12
 * @Description: 1.0
 */
public class T0123 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] left = new int[n];
        int min = prices[0];
        for (int i = 0; i < n; i++) {
            left[i] = i == 0 ? 0 : Math.max(left[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        int[] right = new int[n];
        int max = prices[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            right[i] = i == n - 1 ? 0 : Math.max(right[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        int res = left[n-1];
        for (int i = 0; i < n - 1; i++) {
            res = Math.max(res, left[i] + right[i + 1]);
        }
        return res;
    }
}
